/*Copyright (C) 2013-2021 LZE*/
#include<bits/stdc++.h>
#define INF 0x7fffffff
#define mod 1000000007
#define eps 1e-6
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N = 1000010;
ll n,a[N];

ll version[N] = {0,1};
ll ask_num = 1;

struct TreeNode{
    ll num;
    ll lc,rc;
    TreeNode(){}
}node[N << 2];
ll node_num = 1;
void build(ll p,ll l,ll r){
    if(l == r){
        node[p].num = a[l];
        return;
    }
    ll mid = (l + r) >> 1;
    node[p].lc = ++node_num;
    node[p].rc = ++node_num;
    build(node[p].lc,l,mid);
    build(node[p].rc,mid + 1,r);
    node[p].num = node[node[p].lc].num + node[node[p].rc].num;
}
void update(ll p,ll l,ll r,ll idx,ll var,ll &point){
    // cout << p << " " << l << " " << r << endl;
    if(l == r){
        node[++node_num].num = var;
        point = node_num;
        return;
    }
    ll mid = (l + r) >> 1;
    ++node_num;
    ll now = node_num;
    ll pnt;
    if(idx <= mid){
        update(node[p].lc,l,mid,idx,var,pnt);
        node[now].lc = pnt;
        node[now].rc = node[p].rc;
    }
    else{
        update(node[p].rc,mid + 1,r,idx,var,pnt);
        node[now].lc = node[p].lc;
        node[now].rc = pnt;
    }
    point = now;
    // cout << pnt << " " << now << " " << node[node[now].lc].num << " " << node[node[now].rc].num << " ";
    node[now].num = node[node[now].lc].num + node[node[now].rc].num;
    // cout << node[now].num << endl;
}
ll query(ll p,ll l,ll r,ll L,ll R){
    if(r < L || R < l)return 0;
    if(L <= l && r <= R)return node[p].num;
    ll mid = (l + r) >> 1;
    if(R <= mid){
        return query(node[p].lc,l,mid,L,R);
    }
    else if(L > mid){
        return query(node[p].rc,mid + 1,r,L,R);
    }
    else{
        return query(node[p].lc,l,mid,L,R) + query(node[p].rc,mid + 1,r,L,R);
    }
}
int main() {
    ll m,act,x,y,k;

    ll pnt;

	scanf("%lld%lld",&n,&m);
    for(int i = 1;i <= n;i++){
        scanf("%lld",&a[i]);
    }

    build(1,1,n);

    for(int i = 1;i <= m;i++){
        scanf("%lld",&act);
        switch(act){
            case 1:{
                scanf("%lld%lld",&x,&y);
                pnt = 0;
                update(version[ask_num],1,n,x,y,pnt);
                version[++ask_num] = pnt;
                break;
            }
            case 2:{
                scanf("%lld%lld%lld",&k,&x,&y);
                printf("%lld\n",query(version[k],1,n,x,y));
                break;
            }
        }
    }
	return 0;
}
